/*
 * @(#)Sieve.java	1.0 Apr 26, 2008
 *
 *	The MIT License
 *
 *	Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>
 *
 *	Permission is hereby granted, free of charge, to any person obtaining a copy
 *	of this software and associated documentation files (the "Software"), to deal
 *	in the Software without restriction, including without limitation the rights
 *	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *	copies of the Software, and to permit persons to whom the Software is
 *	furnished to do so, subject to the following conditions:
 *
 *	The above copyright notice and this permission notice shall be included in
 *	all copies or substantial portions of the Software.
 *
 *	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *	THE SOFTWARE.
 */
package org.eoti.math.prime;

import org.eoti.math.MathUtil;

import java.math.BigInteger;
import java.util.*;

public class Sieve
{
	public static void main(String[] args)
			throws Exception
	{
		Sieve s = new Sieve(new BigInteger(args[0]));
		ArrayList<BigInteger> primes = s.getPrimes();
		BigInteger last = primes.get(primes.size()-1);
		String fmt = "%"+ last.toString().length() + "s: %s\n";

		for(int i=0; i<primes.size(); i++)
			System.out.format(fmt, i, primes.get(i));
	}

	protected BigInteger upperBoundary;
	protected BigInteger sqrt;
	protected ArrayList<BigInteger> primes;

	public Sieve(BigInteger upperBoundary)
	{
		this.upperBoundary = upperBoundary;
		sqrt = MathUtil.sqrt(upperBoundary);
		populatePotentialPrimes();
		removeNonPrimes();
	}

	public ArrayList<BigInteger> getPrimes(){return primes;}

	protected void removeNonPrimes()
	{
		BigInteger currentPrime = BigInteger.ONE;
		while(currentPrime.compareTo(sqrt) < 0)
		{
			BigInteger nextPrime = nextPrime(currentPrime);
			if(nextPrime.compareTo(BigInteger.ONE.negate()) == 0)
				return; // done

			removeMultiples(nextPrime);
			currentPrime = nextPrime;
		}
	}

	protected void removeMultiples(BigInteger prime)
	{
		BigInteger multiplier = BigInteger.valueOf(2);
		BigInteger total = multiplier.multiply(prime);
		while(total.compareTo(upperBoundary) < 0)
		{
			primes.remove(total);
			multiplier = multiplier.add(BigInteger.ONE);
			total = multiplier.multiply(prime);
		}
	}

	protected void populatePotentialPrimes()
	{
		primes = new ArrayList<BigInteger>();
		BigInteger i = BigInteger.ONE;
		while(i.compareTo(upperBoundary)<0)
		{
			primes.add(i);
			i=i.add(BigInteger.ONE);
		}
	}

	protected BigInteger nextPrime(BigInteger currentPrime)
	{
		for(BigInteger toCheck : primes)
		{
			if(toCheck.compareTo(currentPrime) > 0)
				return toCheck;
		}

		return BigInteger.ONE.negate();
	}
}
